package com.leetcode.根据数据结构分类.图;

/**
 * @author: ZhouBert
 * @date: 2021/1/25
 * @description: 959. 由斜杠划分区域
 * https://leetcode-cn.com/problems/regions-cut-by-slashes/
 */
public class B_959_由斜杠划分区域 {
	public static void main(String[] args) {
		String[] grid = new String[]{" /", "/ "};
		grid = new String[]{" /",
				"  "};
		B_959_由斜杠划分区域 action = new B_959_由斜杠划分区域();
		int res = action.regionsBySlashes(grid);
		System.out.println("res = " + res);
	}

	/**
	 * 从场景转为 代码 之间的分析比较难。
	 * --
	 * 分析：
	 * 1.每一个方块，从 \ 和 / 上看，被划为 上，下，左，右四个区域。
	 * 2.将大的正方形看成是一个图，那么此题就是求连通分量的个数。
	 *
	 * @param grid
	 * @return
	 */
	public int regionsBySlashes(String[] grid) {
		//正方形的边长
		int n = grid.length;
		//每一个单位格子都被划分为四个区域
		int size = (n * n) << 2;

		//记录边界的索引
		int lastDown = 0, lastRight = 0, preUp = 0, preLeft = 0;
		//本单元格计算的索引
		int up = 0, down = 0, left = 0, right = 0;
		//边界等变量
		int rowInterval = n << 2;
		int colEnd = n - 1, rowEnd = colEnd;

		InnerUnionFind unionFind = new InnerUnionFind(size);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				//1.最小单元格内部整理
				up = (i * n + j) << 2;
				down = up + 1;
				left = down + 1;
				right = left + 1;
				if (grid[i].charAt(j) == ' ') {
					//空白的时候
					unionFind.union(up, down);
					unionFind.union(left, right);
					unionFind.union(up, left);
				} else if (grid[i].charAt(j) == '/') {
					unionFind.union(up, left);
					unionFind.union(right, down);
				} else {
					unionFind.union(up, right);
					unionFind.union(left, down);
				}


				//2.单元格旁边的合并
				//反向操作
				if (i != 0) {
					//说明可以有上边界
					lastDown = down - rowInterval;
					unionFind.union(lastDown, up);
				}
				if (j != 0) {
					//说明有左边界
					lastRight = up - 1;
					unionFind.union(lastRight, left);
				}
				if (j != colEnd) {
					//说明有右边界
					preLeft = left + 4;
					unionFind.union(preLeft, right);
				}
				if (i != rowEnd) {
					//说明有下边界
					preUp = up + rowInterval;
					unionFind.union(preUp, down);
				}
			}
		}
		return unionFind.count;
	}


	class InnerUnionFind {
		int[] parents;
		int[] ranks;
		int count;

		public InnerUnionFind(int capacity) {
			this.parents = new int[capacity];
			this.ranks = new int[capacity];
			for (int i = 0; i < capacity; i++) {
				this.parents[i] = i;
				this.ranks[i] = 1;
			}
			//连通分量的个数
			this.count = capacity;
		}

		public int find(int index) {
			if (index != parents[index]) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}

		public void union(int index1, int index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			count--;
			if (ranks[p1] == ranks[p2]) {
				ranks[p2]++;
				parents[p1] = parents[p2];
			} else if (ranks[p1] < ranks[p2]) {
				parents[p1] = parents[p2];
			} else {
				parents[p2] = parents[p1];
			}
		}

		public boolean isSame(int index1, int index2) {
			return find(index1) == find(index2);
		}
	}
}
